The present invention relates to runtime environments for computer systems; more particularly, the present invention relates to an a runtime environment that distinguishes reference values from non-reference values.
Many prior art runtime environments provide partitioning of registers into volatile registers and non-volatile registers. The partition of registers into volatile and non-volatile is typically performed once and is not subsequently changed. Volatile registers are typically used to pass parameters during subroutine calls and returns, provided the parameters fit. Parameters that do not fit in the volatile registers are passed in memory. Non-volatile registers store information that is maintained across subroutine calls. If a subroutine uses a non-volatile register, the subroutine saves the value stored in the non-volatile register and restores the value prior to returning to the calling routine.
Rigid partitioning of registers into volatile and non-volatile partitions provides predictability as to what registers are to be saved by called routines and what registers are to be saved by calling routines. However, rigid partitioning of registers does not provide information as to which registers are used for references to objects memory and which registers are used for storing values used by a routine or subroutine. For this reason, conservative garbage collection is often used in runtime environments that provide rigid partitioning of registers.
Garbage collection is the automatic recovery of memory space that is no longer required by a computation, routine or subroutine. Thus, garbage is the memory space that has been used, but is no longer required by a computation, routine or subroutine that has not yet been reclaimed by the memory manager of the runtime environment. Conservative garbage collection is based on an algorithm that overestimates the amount of live data in memory where garbage collection takes place. Conservative garbage collection is typically used where a compiler provides little support as to registers and memory locations that provide pointers to objects in memory.
Because overestimation of live data in memory (i.e., conservative garbage collection) results in sub-optimal memory management, support for non-conservative (perfect) garbage collection is desirable. A non-conservative garbage collector can take one of two forms. A non-copying collector that requires that unique references from a stack to a heap be identified so that heap objects that are in use are not accidentally collected. Alternatively, a copying collector additionally requires that non-unique references be identified so that they can be modified if the item referenced moves.
Some prior art runtime environments have provided support for garbage collection by providing tags that indicate whether a register or stack entry is a reference value or a non-reference value. However, maintaining tags increases the overhead required for memory management and in some cases reduces the number of bits available to represent data by using a most significant or least significant bit as a tag.
Prior art runtime environments have also provided support for garbage collection by providing a rigid reference/non-reference partitioning of registers. For example, the 68000 microprocessor available from Motorola, Inc. of Schaumburg, Ill. provides 16 data (non-reference) and 16 address (reference) registers. Runtime environments based on the 68000 provide 16 data and 16 address registers. Rigid reference/non-reference partitioning, however, is not based on the needs of a particular routine or subroutine, and therefore can provide sub-optimal register partitioning.
What is needed is a runtime environment that supports non-conservative garbage collection without the overhead associated with tags or tables to designate reference and non-reference values. The present invention provides such a runtime environment by providing volatile and non-volatile registers, each of which is further partitioned into reference and non-reference registers. The reference/non-reference partitioning of non-volatile registers is accomplished dynamically.
A method and apparatus for distinguishing reference values from non-reference values in a runtime environment is described. A set of volatile registers and a set of non-volatile registers are statically determined. The set of volatile registers is partitioned into reference and non-reference register partitions statically. The set of non-volatile registers is partitioned into reference and non-reference partitions dynamically.